package com.future;

/**
 * Description: 面试题 17.06. 2出现的次数
 * 编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。
 * 示例:
 * 输入: 25
 * 输出: 9
 * 解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/number-of-2s-in-range-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2022/7/20 16:17
 */
public class Solution_17_06 {

    public static void main(String[] args) {
        int n = 559366752;
        System.out.println(System.currentTimeMillis());
        System.out.println(numberOf2sInRange(n));
        System.out.println(System.currentTimeMillis());
        System.out.println(numberOf2sInRange2(n));
        System.out.println(System.currentTimeMillis());
    }

    /**
     * 暴力方法
     *
     * @param n
     * @return
     */
    public static int numberOf2sInRange2(int n) {
        if (n < 2) {
            return 0;
        }
        if (n < 12) {
            return 1;
        }
        if (n < 20) {
            return 2;
        }
        int ans = 2;
        for (int num = 20; num <= n; num++) {
            int copyNum = num;
            while (copyNum != 0) {
                int mod = copyNum % 10;
                if (mod == 2) {
                    ans++;
                }
                copyNum /= 10;
            }
        }
        return ans;
    }


    /**
     * 参考
     *
     * @param n
     * @return
     */
    public static int numberOf2sInRange(int n) {
        int ans = 0;
        int count;
        int rest;
        for (int i = 1; i <= n; i *= 10) {
            count = (n / (i * 10)) * i;
            rest = Math.min(Math.max(n % (i * 10) - (i * 2 - 1), 0), i);
            ans += (count + rest);
        }
        return ans;
    }


}
